package leetcode.editor.cn.q1_300.q;

/**
 * @author qidi
 * @date 2021-11-11 14:12:10
 */
class Q0037_SudokuSolver {

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public void solveSudoku(char[][] board) {
            boolean[][] row = new boolean[9][9];
            boolean[][] col = new boolean[9][9];
            boolean[][] box = new boolean[9][9];

            for (int i = 0; i < 9; i++) {
                for (int j = 0; j < 9; j++) {
                    if (board[i][j] == '.') continue;

                    int k = board[i][j] - 49;
                    row[i][k] = true;
                    col[j][k] = true;
                    box[i / 3 * 3 + j / 3][k] = true;
                }
            }

            process(board, row, col, box, 0);
        }

        private boolean process(char[][] board, boolean[][] row, boolean[][] col, boolean[][] box, int n) {
            if (n == 81) return true;

            int i = n / 9;
            int j = n % 9;
            if (board[i][j] != '.') return process(board, row, col, box, n + 1);

            int k = i / 3 * 3 + j / 3;
            for (int num = 0; num < 9; num++) {
                if (row[i][num] || col[j][num] || box[k][num]) continue;
                board[i][j] = (char) (num + '1');
                row[i][num] = col[j][num] = box[k][num] = true;
                if (process(board, row, col, box, n + 1)) return true;
                row[i][num] = col[j][num] = box[k][num] = false;
            }
            board[i][j] = '.';
            return false;
        }

    }
    //leetcode submit region end(Prohibit modification and deletion)


    public static void main(String[] args) {
        Solution solution = new Q0037_SudokuSolver().new Solution();
        char[][] chars = new char[][]{
                {'.', '.', '9', '7', '4', '8', '.', '.', '.'},
                {'7', '.', '.', '.', '.', '.', '.', '.', '.'},
                {'.', '2', '.', '1', '.', '9', '.', '.', '.'},
                {'.', '.', '7', '.', '.', '.', '2', '4', '.'},
                {'.', '6', '4', '.', '1', '.', '5', '9', '.'},
                {'.', '9', '8', '.', '.', '.', '3', '.', '.'},
                {'.', '.', '.', '8', '.', '3', '.', '2', '.'},
                {'.', '.', '.', '.', '.', '.', '.', '.', '6'},
                {'.', '.', '.', '2', '7', '5', '9', '.', '.'}
        };
        solution.solveSudoku(chars);

        for (int i = 0; i < chars.length; i++) {
            for (int j = 0; j < chars[i].length; j++) {
                System.out.print(chars[i][j] + ", ");
            }
            System.out.println();
        }
    }
}